package sort;
import java.util.Arrays;

/**
 * @Classname MergeSort
 * @Author happytaohaha
 * @Date 2020/2/29
 * @Description 归并排序   复杂度O(nlogn)
 */
public class MergeSort {

    public static int[] mergeSort(int[] array) {
        int left = 0;
        int right = array.length-1;
        int[] temp = array.clone();
        split(array,temp,left,right);
        return array;
    }

    //分开
    public static void split(int[] array,int[] temp,int left, int right){
        if (left >= right){
            return;
        }
        int mid = (left+right)/2;
        split(array,temp,left,mid);
        split(array,temp,mid+1,right);
        merge(array,temp,left,mid,right);
    }

    //合并
    public static void merge(int[] array,int[] temp,int left, int mid, int right){
        int i = left;
        int index = left;
        int j = mid+1;
        while (i <= mid && j <= right){
            if(array[i]<array[j]){
                temp[index++]= array[i++];

            }else{
                temp[index++]= array[j++];
            }
        }
        while (i <= mid){
            temp[index++] = array[i++];
        }
        while (j <= right){
            temp[index++] = array[j++];
        }
        for(i = left; i <= right; i++){
            array[i] = temp[i];
        }
    }


    public static void main(String[] args) {
        System.out.println(Arrays.toString(mergeSort(new int[]{9,8,7,6,5,4,3,2,1})));
    }
}
